package com.zy.find;

import java.util.List;
import java.util.Objects;

/**
 * __|__ __|__
 * _|_   _|_
 * .---. .---.
 * |___| |___|
 * _\_/_ _\_/_
 * _X_   _X_
 * |   | |   |
 * |___| |___|
 *
 * @Author zhaoyi
 * @date 2020/4/9
 * 二分查找
 *      这是一个错误的示例
 *      这是一个错误的示例
 *      这是一个错误的示例
 *      这是一个错误的示例
 */
public class BinarySearch {

    /**
     * 二分查找
     * 返回数组下标
     */
    public int find(List<Integer> list, Integer t) {

        if (t < list.get(0) || t > list.get(list.size() - 1)) {
            throw new RuntimeException("找不到");
        }

        return findRecursive(list, t, 0, list.size() - 1);
    }

    private int findRecursive(List<Integer> list, Integer t, int left, int right) {

        if (Objects.equals(list.get(left), t)) {
            return left;
        }

        if (Objects.equals(list.get(right), t)) {
            return left;
        }

        //避免(a+b)/2当 ab很大时超过int的容量
        int mediate = (list.get(left) + list.get(right) - list.get(left)) >> 1;

        if (Objects.equals(list.get(mediate), t)) {
            return mediate;
        }

        if (list.get(mediate) > t) {
            return findRecursive(list, t, left, mediate);
        } else {
            return findRecursive(list, t, mediate, right);
        }
    }

}
